package com.cqs.leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/9/8
 */
public class BracketLCCI {

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        generateParenthesis(n, n, "", list);
        return list;
    }


    private void generateParenthesis(int left, int right, final String tmp, List<String> list) {
        if (left == 0) {
            StringBuilder s = new StringBuilder(tmp);
            for (int i = 0; i < right; i++) {
                s.append(")");
            }
            list.add(s.toString());
            return;
        }
        //下一个放左括号
        generateParenthesis(left - 1, right, tmp + "(", list);
        //下一个放右括号
        if (left < right) {
            generateParenthesis(left, right - 1, tmp +")", list);
        }
    }

    public static void main(String[] args) {
        BracketLCCI bracket = new BracketLCCI();
        List<String> list = bracket.generateParenthesis(3);
        System.out.println(list);
    }
}
